#include<stdio.h>


void maxHeap(int *a,int t,int len)
{
    int left = 2 * t + 1;
    int right = left + 1;
    int max = t;
    if(left < len && a[left] > a[t])
        max = left;
    if(right < len && a[right] > a[max])
        max = right;
    if(max != t)
    {
        int tmp;
        tmp = a[t];
        a[t] = a[max];
        a[max] = tmp;
        maxHeap(a,max,len);
    }
}

 void  buildHeap(int *a,int len)
 {
     int k = len/2;
     for(; k >= 0; k--)
        maxHeap(a,k - 1,len);
 }


void heapSort(int *a,int len)
{

    for(; len > 1; len--)
    {
        buildHeap(a,len);
        int tmp = 0;
        tmp = a[0];
        a[0] = a[len-1];
        a[len - 1] = tmp;
    }
}


int main()
{
    int a[] = {2,6,1,8,3,9,4,7,5,0};
    heapSort(a,10);
    int i = 0;
    for(; i < 10; i++)
        printf("%d ",a[i]);
    return 0;
}



